#define _CRT_SECURE_NO_WARNINGS  1

/*

#include<stdio.h>
#define Mul(x,y) ++x*++y
	int main()
	{
		int a = 1;
		int b = 2;
		int c = 3;
		printf("%d", Mul(a + b, b + c));
		return 0;
	}


#include <stdio.h>
#define a 10
	void foo();
	int main()
	{
		printf("%d..", a);
		foo();
		printf("%d", a);
		return 0;
	}
	void foo() {
#undef a
#define a 50
	}






#include<stdio.h>
#define A 100
void s();
void b();
int main()
{
	printf("%d\n", A);
	s();
	printf("%d\n", A);
	b();

}

void s()
{
	#undef A
	
	#define A 50
}

void b()
{
	printf("%d\n", A);

}

*/

#include <stdio.h>

int main()
{
	int n = 0;
	scanf("%d", &n);

	int arr[1000001];
	arr[0] = 1;
	arr[1] = 2;

	for (int i = 2; i < 1000001; i++)
	{
		arr[i] = (2 * arr[i - 1] + arr[i - 2]) % 32767;
	}


	while (n--)
	{
		int x = 0;
		scanf("%d", &x);
		printf("%d\n", arr[x - 1]);
	}
	return 0;
}